The next thing we looked at yesterday was planning complexity.

Planning complexity is essentially looking at worst-case scenarios for planning and we

had it before, we have satisfying planning and optimal planning and you would think that

optimal planning is much harder than satisfying planning.

Turns out that they're in the same complexity class, which means essentially up to the granularity

of measurement of exponential effects, which is really what you're going to get for PSPACE,

they're just as hard one as the other.

But then if you're accepting algorithms that are equal, if they have exponential factors

of difference, then you shouldn't be surprised that you put them into the same complexity

class.

In a way, complexity class gives us good estimates of how hard things are, but also it's a relatively

coarse-grained description.

Especially, it's kind of nice when you have to decide between linear and quadratic or

something like this.

There it's a very good thing.

Whereas when things get hard, as they do in AI, you can only kind of distinguish between

extremely hard and terrible, maybe still impossible.

It's good to have the theoretical results, but they're only worst case and they get coarser

and coarser in their classification height.

Of course, the only reason we're doing AI is because we're not scared by things like

Plan X being PSPACE hard.

By conventional wisdom, that's too hard.

Sometimes we can actually do something and AI is really about this.

We can do something even though it's too hard.

But in the worst case, we'll fail on that.

Humans fail on those as well, unless they know something more about this.

But in the average case, we can do quite well.

That's really what we're after.

You should probably take complexity results with the proper appreciation, but still it's

good to have them.

We had Plan X, which is essentially satisfying.

Planning is PSPACE and Plan LEN, which is, is there a plan of given length B, which basically

corresponds to optimizing planning, is also PSPACE complete, which means they're essentially

the same.

Mostly we're interested in the practicalities of this.

In the practicalities, in the good cases, optimizing is still harder than satisfying

planning, which is why most algorithms try to satisfy.

By approximation, I'm getting ahead that way.

In practice, we convince ourselves that many of these problems are actually hard.

This is where NP-hardness comes from.

Even in practice, you have these kind of problems.

Think about what people are doing in a warehouse, an unorganized warehouse.

You're getting stuff in and you want to have it out in a different way, so you have to

restack stuff.

Stacking stacks that high, and many of them is not actually uncommon.

Think about the back room of your local Aldi.

They're doing things like that.

As far as I know, Aldi doesn't use planning.

They use natural intelligence there because they buy natural intelligence cheap.

Whereas when it gets bigger in big warehouses like Amazon or so, they have ways of doing